package com.middle;

import java.util.*;
import java.util.stream.Collectors;

/**
 * @ClassName Test187
 * @Description
 * @Author xinggh
 * @Date 2020/8/28 22:35
 * @Version 1.0
 **/
public class Test187 {
    /**
     * 187. 重复的DNA序列
     * 所有 DNA 都由一系列缩写为 A，C，G 和 T 的核苷酸组成，例如：“ACGAATTCCG”。
     * 在研究 DNA 时，识别 DNA 中的重复序列有时会对研究非常有帮助。
     * <p>
     * 编写一个函数来查找目标子串，目标子串的长度为 10，且在 DNA 字符串 s 中出现次数超过一次。
     */

    public List<String> findRepeatedDnaSequences(String s) {

        if (s.length() <= 10) {
            return Collections.emptyList();
        }
        Map<String, Integer> map = new HashMap();
        for (int i = 0; i < s.length() - 10; i++) {
            String s1 = s.substring(i, i + 10);
            for (int j = i + 1; j <= s.length() - 10; j++) {
                String s2 = s.substring(j, j + 10);
                if (check(s1, s2)) {
                    if (map.containsKey(s1)) {
                        Integer integer = map.get(s1);
                        map.put(s1, integer++);
                    } else {
                        map.put(s1, 1);
                    }

                }
            }
        }
        List<String> collect = map.keySet()
                .stream().filter(x -> map.get(x) > 0).collect(Collectors.toList());
        return collect;

    }

    /**
     * 比较两个字符串
     *
     * @param s1
     * @param s2
     * @return
     */
    public boolean check(String s1, String s2) {
        if (s1.length() != s2.length()) {
            return false;

        }
        int l1 = s1.length();
        int i = 0;
        while (i < l1) {
            if (s1.charAt(i) == s2.charAt(i)) {
                i++;
            } else {
                return false;
            }

        }
        return true;
    }


    /**
     * 官方题解
     *
     * @param args
     */
    public List<String> findRepeatedDnaSequences1(String s) {
        int L = 10, n = s.length();
        HashSet<String> seen = new HashSet(), output = new HashSet();

        // iterate over all sequences of length L
        for (int start = 0; start < n - L + 1; ++start) {
            String tmp = s.substring(start, start + L);
            if (seen.contains(tmp)) output.add(tmp);
            seen.add(tmp);
        }
        return new ArrayList<String>(output);
    }

    public static void main(String[] args) {
        Test187 test187 = new Test187();
        String s = "AAAAAAAAAAA";
        System.out.println(test187.findRepeatedDnaSequences(s));
    }
}
